COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003	.hd206 SPRING 1978
C00004 00004	#. The depth of an S-expression is given by the length of the longest 
C00008 ENDMK
C⊗;
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
.place heading
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.place text
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.LSPFONT
.basicops 
.itemmac 1;
.
.PORTION MAINPORTION
.hd206 SPRING 1978
.PAGE ← 1
.cb MIDTERM EXAM
.ITEM←0

	Write definitions for the following functions or predicates.

	You may use any books or notes that you wish on this test.
You may use either external or internal notation for your definitions.

.indent 0,4
#. The ⊗depth of an S-expression is given by the length of the longest 
path to an atom.  Thus ⊗⊗depth[$$A$]=0⊗ and ⊗⊗depth[$$(((A.B).C).D)$]=3⊗.

#. ⊗balanced[x] is true if and only if the S-expression is balanced.
We say that an S-expression is balanced if it is an atom or if
⊗⊗depth[qa x]⊗ and ⊗⊗depth[qd x]⊗ differ by at most 1
and qa ⊗x and qd ⊗x are both balanced.  Thus ⊗⊗balanced[$$((A.B).C)$]⊗ 
is true but ⊗⊗balanced[$$(((A.B).C).D)$]⊗ is false.

#.  Let ⊗g be an undirected graph represented as a list of lists as described
in Chapter I.  

    ##.  ⊗deleteα_vertex[v,g]  returns a graph ⊗g1 with vertices those of
⊗g omitting ⊗v, and edges the same as ⊗g omitting those connecting ⊗v to 
another vertex.
.break
    ##.  ⊗complement[g]  returns a graph ⊗g1 with vertices the same as ⊗g, but
vertices ⊗v and ⊗w are joined by an edge in ⊗g1 if and only if they are not
joined by an edge in ⊗g.  


	For example if ⊗g is given by $$((A_B_D)_(B_C_D_A)_(C_D_B)_(D_A_B_C))$ then we have:
.begin nofill

		⊗⊗deleteα_vertex[$$A$,g]=⊗$$((B_C_D)_(C_D_B)_(D_B_C))$
		⊗⊗         complement[g]=⊗$$((A_C)_(B)_(D)_(C_A))$.
.end

#.  Consider arithmetic expressions as represented in Ch I. Namely an
expression is 
.begin nofill

	(i) a number (satisfies ⊗numberp), 
	(ii) a variable (not a number and satisfies qqat),
	(iii) a sum : $PLUS . < list of expressions > or
	(iv) a product : $TIMES . < list of expressions >.

    (For simplicity, assume the sum and product lists always have at least 2 elements.)
.end
	The function ⊗sop converts such expressions into sum of products
form, eg. the resulting expression is either a monomial 
or a sum of monomial terms which has the form $$PLUS$_._<list_of_monomials>.
A monomial is either a number, a variable, or a product of the 
form $$TIMES$_._< list of numbers or variables >.
Thus, 
.begin nofill
		⊗⊗sop[$$(TIMES_(TIMES_X_3)_(PLUS_Y_Z)_(PLUS_Y_1))$]=⊗
			$$(PLUS_(TIMES_X_3_Y_Y)_(TIMES_X_3_Y_1)_(TIMES_X_3_Z_Y)_(TIMES_X_3_Z_1))$.
.end
	Notice that simplification is not required.